Copyright ã1995 by NeXT Computer, Inc.  All Rights Reserved.

IXStore

Inherits From:	Object

Declared In:	store/IXStore.h

Class Description

IXStore is a transaction based, compacting storage allocator designed for data-intensive applications.  Its main features include compaction and relocatability of storage, for reducing and optimizing memory usage; transaction management, for making compound operations atomic and for ensuring data integrity; and concurrency control, for ensuring safe access to shared storage.

An IXStore manages a single memory-based heap.  Blocks of storage managed by the IXStore are addressed indirectly by the client, through unsigned integers called handles.  To gain access to the contents of a block, the client must open the block for reading or writing.  An IXStore opens a block by resolving the block's handle into a pointer.  While a block is open, client code is free to address its contents through the pointer, and can safely assume that the block won't move.  When a block is closed, however, the IXStore is free to move it in order to compact storage; pointers cached by the client may therefore become invalid.

The contents of an IXStore are relocatable to and from other instances of IXStore and its subclasses.  Since block handles are indirect reference to data, it's possible to retrieve the contents of an IXStore as a single unit and to store that unit in another IXStore without invalidating handle-based referential data structures residing in the IXStore, like linked lists or trees.  This makes it easy to copy complex structures, or to quickly save them to a file.

IXStore implements transactions, allowing several operations to be grouped together in such a way that either all of them take effect, or none of them does.  This helps to ensure semantic integrity by making compound operations atomic, and provides a convenient way to undo a series of changes.  The use of transactions also ensures data integrity against process and system crashes when used with a persistent storage medium; for example, IXStoreFile, a subclass of IXStore, keeps its storage in a UNIX file.  This means that if a system loses power, the IXStoreFile's contents can be recovered intact on power up, in the state they were in after the last transaction that actually finished.  For more details on persistence, see the IXStoreFile class specification.

IXStore is thread-safe.  All methods perform the locking needed to ensure the integrity of shared data structures when the IXStore is addressed by different Mach threads.  Clients of an IXStore need only synchronize higher-level operations to ensure semantic integrity (see the IXBTree class specification for an example of this).

It's possible for two or more instances of IXStore to share the same contents; these instances are called store contexts.  IXStore mediates access to the blocks among multiple contexts through transactions.  No block may be accessed by more than one context at a time, and an open block becomes available again only when the transaction that opened it aborts, or when the last outstanding transaction on the context that opened it is committed.  A block opened only for reading, however, becomes available as soon as it's closed.  When a context tries to open a block that's already been opened by another context, an exception is raised.  This supports the use of deadlock avoidance strategies by the client.

Using Transactions

To start a transaction, send startTransaction to the IXStore.  This defines a checkpoint your code can go back to if it has to undo changes.  Transactions aren't enabled by default; the first time one is started, the IXStore permanently enables transactions.  Your code can check whether transactions have been enabled with areTransactionsEnabled.  You may want to do this if your code  is invoked by higher level methods that determine the transaction management policy for the application.  For example, IXBTree uses areTransactionsEnabled to determine whether or not to invoke startTransaction before responding to an empty message.

Using transactions makes updates slower, since blocks must be copied when they're opened for writing.  On the other hand, in the case of an IXStoreFile, it's nearly certain that the storage will be unrecoverable following a crash if your code doesn't use transactions.  Always use IXStore without transactions, unless you need undo capability, since its contents are always destroyed by a crash.  Always use IXStoreFile with transactions, except for data that can be easily reconstructed, such as an index.

Once you've started a transaction, your code can open blocks and make changes to them, or even start another transaction inside the previous one.  The nestingLevel method tells how many transactions are pending on the context.  This is important if a transaction has already been started by a method that invokes yours, so that yours doesn't finish a transaction that the invoking method is still working on.  The nesting level also determines when blocks are made available to other contexts.  Modified blocks are made available when the nesting level becomes 0Ðthat is, when the last transaction is committed, or when the transaction that opened them is aborted.  Unmodified blocks are made available when they're closed.

At any point in a transaction, your code can send abortTransaction to the IXStore.  This undoes everything you've done up to that point in the current transaction: created blocks are destroyed, freed blocks are recovered, block resizes are undone, and any changes made to blocks opened after the corresponding startTransaction message are undone and those blocks are closed.  Also, any blocks opened in that transaction are made available to other contexts.

When your code is ready to commit its changes, it sends commitTransaction to the IXStore.  This closes all blocks opened since the last startTransaction, and makes sure all changes are recorded.  Changes aren't flushed immediately, however, if the transaction is nested within another one.  This means that changes committed by nested transactions can be undone by their parents.  If the commitTransaction results in a nesting level of 0, then all pending changes are physically flushed, making them permanent, and all blocks that had been opened by the committing context are made available to other contexts.

One restriction on transaction nesting is that changes to a block are associated with the transaction that opened the block.  That is, within a nested transaction, changes made to any block opened by an outer transaction are associated with the outer transaction, not the nested transaction.  The changes aren't undone when the inner transaction is aborted; the outer transaction must be aborted to undo the changes.  Changes made to any block opened by the nested transaction, however, are associated with the nested transaction, not the outer transaction, and can be undone by aborting either transaction.

Note that if your code makes changes outside any transaction while transactions are enabled, an enclosing transaction is started automatically.  The next invocation of startTransaction, if any, before an intervening abort or commit, simply picks up this enclosing transaction, and reports a nesting level of 1.  Thus, if nesting isn't needed, your code can simply enable transactions initially with a pair of startTransaction/commitTransaction messages, and thereafter use only commitTransaction to mark transaction boundaries, leaving  transactions implicitly begin with the first modification following each commit.

When using an IXStoreFile without transactions, try to cluster your updates into small windows of activity, and invoke commitTransaction at the close of each window to flush them immediately, as this will minimize the probability of damage in the event of a system crash or power loss.  Also note that any modifications that haven't been committed are aborted when an IXStore is freed.

Instance Variables

unsigned int changeCount;

unsigned int nestingLevel;

unsigned int queueForward;

unsigned int queueReverse;

struct StoreBroker *storeBroker;

changeCount 	The number of the changes made to the IXStore's contents since the IXStore was created.

nestingLevel 	The number of the current nested transaction.

queueForward 	For internal use by the IXStore.

queueReverse 	For internal use by the IXStore.

storeBroker 	For internal use by the IXStore.

Method Types

Initializing, copying, and freeing instances
- init
- copy
- free

Creating, copying, and freeing blocks
- createBlock:ofSize:
- copyBlock:atOffset:forLength:
- freeBlock:

Opening and closing blocks	- openBlock:atOffset:forLength:
- readBlock:atOffset:forLength:
- closeBlock:

Managing block sizes	- resizeBlock:toSize:
- sizeOfBlock:

Using transactions	- startTransaction
- abortTransaction
- commitTransaction
- areTransactionsEnabled
- nestingLevel
- changeCount

Accessing the contents	- getContents:andLength:
- setContents:andLength:

Reducing memory consumption	- compact

Instance Methods

abortTransaction

- abortTransaction

Reverts the IXStore to the state it was in before the last time it received a startTransaction message, if transactions are enabled.  Discards all changes made to blocks that were opened by the current transaction (even if they've been closed), closes those blocks if necessary, and makes them available to other contexts.  Any blocks created by the current transaction are destroyed, any blocks freed are reclaimed, and any blocks resized are restored to their previous size.  The current transaction is terminated, and the transaction in effect, if any, when the current transaction was started is made the current transaction.  If the nesting level is 1 (that is, no transaction is pending), the state reverts to the last time a commitTransaction was received.  Returns self.

Blocks opened by an enclosing transaction are not affected, even if their contents have been changed since the receipt of the last startTransaction message.  If transactions aren't enabled, only the block creations and freeings performed since the last commitTransaction message are reverted; changes made to the contents of blocks aren't undone.  Even if your code never uses startTransaction, it should periodically send commitTransaction to establish a checkpoint for abortTransaction.

This method increases the change count of the IXStore, indicating that a change in state has occurred which may have closed blocks.

See also:  - commitTransaction, - startTransaction, - nestingLevel, - changeCount, - closeBlock:

areTransactionsEnabled

- (BOOL)areTransactionsEnabled

Returns YES if transactions are enabled for the IXStore (that is, if the IXStore was ever sent a startTransaction message).  Otherwise, it returns NO.  You should use this method if you're not sure whether or not to send startTransaction messages, or when invoked by higher-level code that establishes the transaction management policy.

The transaction management policy is a property of the contents of an IXStore.  If your code copies the contents of an IXStore that has transactions enabled into an IXStore that doesn't, transactions will be enabled for the receiving IXStore.

See also:  - startTransaction, - nestingLevel

changeCount

- (unsigned int)changeCount

Returns the number of commitTransaction and abortTransaction messages received by the IXStore since it was created.  That is, this number indicates the number of changes made to the IXStore's contents since the run-time object was initialized.

This method is useful for determining if cached pointers to the contents of opened blocks are still valid, so the overhead of the block opening methods can be avoided.  For example, if an object needs to repeatedly access the same block within a transaction, it can cache the pointer to the block's contents when it opens the block, along with the change count.  From then on, whenever the object needs to access the block, it can check the IXStore's change count; if the change count hasn't increased, then no commits or transactions have occurred since the block was opened, which means that the cached pointer is still valid, and the object can use the pointer safely without having to open the block againÐunless, of course, the object itself has since closed the block.  (The use of this method by IXBTreeCursor accounts for a 40% performance improvement on sequential key reads when all pages are in memory.)

See also:  - nestingLevel, - abortTransaction, - commitTransaction

closeBlock:

- closeBlock:(unsigned int)aHandle

Closes the block identified by aHandle.  This allows the IXStore to relocate the block if needed.  Changes to the block don't take effect until the transaction that opened it is committed; similarly, changes aren't undone until the transaction that opened the block is aborted.  Open blocks are automatically closed when the transaction that opened them is either committed or aborted.  Returns self.

Note:  Closing a block that was opened for writing does not make it available to other contexts; the transaction in which the block was opened must be aborted, or pending transactions committed until the nesting level is 0, for it to become available again.  Blocks opened for reading become available when closed, since there are no changes to protect.

See also:  - openBlock:atOffset:forLength:, - readBlock:atOffset:forLength:, - startTransaction, - commitTransaction, - abortTransaction

commitTransaction

- commitTransaction

Commits all changes made to blocks opened since the last startTransaction, closes the blocks.  If the nesting level becomes 0, makes the blocks available to other contexts.  Any creations, freeings or resizes performed since the startTransaction are also committed.  The current transaction is terminated, and the enclosing transaction, if any, becomes the current transaction.  Returns self.

Your code may use this message even if transactions aren't enabled; the reversal of block-level operations (creating and freeing) is supported even in the absence of transactions.  commitTransaction commits all such changes made since the last commitTransaction, and abortTransaction cancels all such changes made since the last commitTransaction.  If transactions aren't enabled, this method closes all open blocks, making them available to other contexts, and commits all outstanding creates and frees.

This method increases the change count of the IXStore, indicating that a change in state has occurred which may have closed blocks.

See also:  - abortTransaction, - startTransaction, - changeCount, - closeBlock:

compact

- compact

Compacts the contents of the IXStore so that they consume as little storage as possible.  This method moves blocks around physically within the IXStore, and so may take some time to complete.  The amount of storage consumed may be reduced by as much as 50%.  Returns self.

If this method is invoked while transactions are pending, the actual compaction will be postponed until there are no transactions outstanding.  When used with IXStoreFile, this method actually reduces the size of the file.  Compaction also may occur automatically.  This won't occur unless the IXStore consumes at least 16 MB of storage, and may not occur until much more storage is actually consumed.

copy

- copy

Creates and returns a new store context, which addresses the same storage as the original.  Changes made by either context will affect the shared storage, and will be reflected in both contexts.

If you want to create a completely independent duplicate of an IXStore, you can use getContents:andLength: and setContents:andLength: as follows:

IXStore      *aStore, *twinStore;
vm_address_t theStorage;
vm_size_t    theLength;

[aStore compact]; // Makes the transfer more efficient.
[aStore getContents:&theStorage andLength:&theLength];
twinStore = [[IXStore alloc] init];
[twinStore setContents:theStorage andLength:theLength];

This technique is also effective for saving the contents of an IXStore into an IXStoreFile.

See also:  - getContents:andLength:, - setContents:andLength:

copyBlock:atOffset:forLength:

- (unsigned int)copyBlock:(unsigned int)aHandle
atOffset:(unsigned int)anOffset
forLength:(unsigned int)aLength

Returns a handle to a new block whose contents are identical to the region of the block identified by aHandle specified by anOffset and aLength.

If there is no block identified by aHandle, IX_NotFoundError is raised.  If the block has been opened by another context, IX_LockedError is raised.  See the class description for more information on when a block becomes available to other contexts.

See also:  - openBlock:atOffset:forLength:, - readBlock:atOffset:forLength:, - abortTransaction, - commitTransaction, - closeBlock:

createBlock:ofSize:

- createBlock:(unsigned int *)aHandle ofSize:(unsigned int)size

Creates a new block of size bytes and returns its handle by reference in aHandle.  The new block is guaranteed to be zeroed.  If you create a block of size vm_page_size or more, it's guaranteed to be page-aligned (vm_page_size is declared in the header file mach/mach_init.h).  It isn't possible to create a block of size 0.  Returns self.

free

- free

Frees the IXStore.  The storage substrate is also freed if there are no other store contexts addressing it.  Returns nil.

See also:  - freeBlock:

freeBlock:

- freeBlock:(unsigned int)aHandle

Removes and frees the block identified by aHandle.  Returns self.

If there is no block identified by aHandle, IX_NotFoundError is raised.  If the block has been opened by another context, IX_LockedError is raised.  See the class description for more information on when a block becomes available to other contexts.

See also:  - free, - abortTransaction, - commitTransaction, - closeBlock:

getContents:andLength:

- getContents:(vm_address_t *)theContents andLength:(vm_size_t *)aLength

Returns by reference the address and length of a copy of the IXStore's contents.  theContents is a copy-on-write image of the original (vm_address_t is declared in the header file mach/mach_types.h).  Returns self.

Your code can use this method along with setContents:andLength: to create an independent copy of an IXStore (see the copy method description for an example).  Be sure to compact the IXStore before invoking this method, so that the amount of memory copied is as small as possible.  These methods also provide an efficient means of saving the contents of an IXStore into an IXStoreFile.

getContents:andLength: must not be invoked when transactions are pending; if it is, IX_ArgumentError is raised.  Your code should also not invoke this method while any blocks are open outside the scope of a transaction (since they may have been changed).

See also:  - setContents:andLength:, - copy

init

- init

Initializes a new IXStore with zero capacity and transactions not enabled.  This is the designated initializer for the IXStore class.  Returns self.

nestingLevel

- (unsigned int)nestingLevel

Returns the number of the transactions pending against the IXStore.  If transactions aren't enabled, this method always returns 0.

See also:  - abortTransaction, - commitTransaction, - areTransactionsEnabled, - startTransaction

openBlock:atOffset:forLength:

- (void *)openBlock:(unsigned int)aHandle
atOffset:(unsigned int)anOffset
forLength:(unsigned int)aLength

Returns a pointer to a region of the block identified by aHandle, beginning at anOffset and of aLength bytes, after opening it for writing.  If your code writes outside of the opened area, your data may become corrupt.  Neither abortTransaction nor commitTransaction will restore data damaged in this manner.

Note:  Unless it's certain that the store is memory-based, your application should assume that the data in the block is big-endian, and convert it to and from host endian-ness as needed.

If there is no block identified by aHandle, IX_NotFoundError is raised.  If the block has been opened by another context, IX_LockedError is raised.  See the class description for more information on when a block becomes available to other contexts.

Note:  When using IXStoreFile, you shouldn't use vm_copy() to write data into a block.  See the IXStoreFile class specification for more details.

See also:  - readBlock:atOffset:forLength:, - freeBlock:, - abortTransaction, - commitTransaction, - closeBlock:

readBlock:atOffset:forLength:

- (void *)readBlock:(unsigned int)aHandle
atOffset:(unsigned int)anOffset
forLength:(unsigned int)aLength

Returns a pointer to a region in the block identified by aHandle, beginning at anOffset and of aLength bytes, after opening it for reading.  It's assumed that your code won't alter the block.  If your code does alter the block, your data may become corrupt, and neither abortTransaction nor commitTransaction will restore data damaged in this manner.

Note:  Unless it's certain that the store is memory-based, your application should assume that the data in the block is big-endian, and convert it to host endian-ness as needed.

If there is no block identified by aHandle, IX_NotFoundError is raised.  If the block has been opened by another context, IX_LockedError is raised.  See the class description for more information on when a block becomes available to other contexts.

See also:  - openBlock:atOffset:forLength:, - freeBlock:, - abortTransaction, - commitTransaction, - closeBlock:

resizeBlock:toSize:

- resizeBlock:(unsigned int)aHandle toSize:(unsigned int)aSize

Resizes the block identified by aHandle to aSize.  Returns self.

If there is no block identified by aHandle, IX_NotFoundError is raised.  If the block has been opened by another context, IX_LockedError is raised.  See the class description for more information on when a block becomes available to other contexts.

See also:  - sizeOfBlock:, - openBlock:atOffset:forLength:, - readBlock:atOffset:forLength, - abortTransaction, - commitTransaction, - closeBlock:

setContents:andLength:

- setContents:(vm_address_t)someContents andLength:(vm_size_t)aLength

Replaces the contents of the IXStore with the contents specified by someContents and aLength.  The original contents of the IXStore are lost.  someContents should be a virtual memory image retrieved by getContents:andLength: (vm_address_t is declared in the header file mach/mach_types.h).  The IXStore assumes responsibility for freeing the virtual memory image, and may simply use it directly.  Contents copied in this manner between instances of IXStore are shared as copy-on-write data.  Returns self.

Your code can use this method along with getContents:andLength: to create an independent copy of an IXStore (see the copy method description for an example).  These methods also provide an efficient means of saving the contents of an IXStore into an IXStoreFile.

setContents:andLength: must not be invoked when transactions are pending; if it is, IX_ArgumentError is raised.

See also:  - getContents:andLength:

sizeOfBlock:

- (unsigned int)sizeOfBlock:(unsigned int)aHandle

Returns the size, in bytes, of the block identified by aHandle.

If there is no block identified by aHandle, IX_NotFoundError is raised.  If the block has been opened by another context, IX_LockedError is raised.  See the class description for more information on when a block becomes available to other contexts.

See also:  - resizeBlock:toSize:, - openBlock:atOffset:forLength:, - readBlock:atOffset:forLength, - abortTransaction, - commitTransaction, - closeBlock:

startTransaction

- (unsigned int)startTransaction

Begins a new transaction, which will be aborted or committed before all other outstanding transactions on the receiving context.  If transactions aren't enabled for the IXStore, they're permanently enabled.  Returns a number identifying the new transaction, and indicating the number of transactions outstanding, including the new one.  This is the same value returned by the nestingLevel method.  For example, if the nesting level is 0 and the IXStore receives startTransaction three times, the invocations of the method will return, in order, 1, 2, 3.

See also:  - abortTransaction, - commitTransaction, - areTransactionsEnabled, - nestingLevel